package leetcode_链表;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU 缓存
 * 算法：双向链表 + 哈希表
 *
 * @author yezh
 * @date 2023/6/5 16:14
 */
public class _146 {

    public static class LRUCache {

        ListNode head;
        ListNode tail;
        Map<Integer, ListNode> map;
        int capacity;

        public LRUCache(int capacity) {
            head = new ListNode();
            tail = new ListNode();
            head.next = tail;
            tail.pre = head;
            map = new HashMap<>(capacity);
            this.capacity = capacity;
        }

        public int get(int key) {
            ListNode listNode = map.get(key);
            if (listNode == null) return -1;
            listNode.del().addAfter(head);
            return listNode.val;
        }

        public void put(int key, int value) {
            ListNode listNode = map.get(key);
            if (listNode != null) {
                listNode.val = value;
                listNode.del();
            } else {
                listNode = new ListNode(key, value);
                if (map.size() == capacity) map.remove(tail.pre.del().key);
                map.put(key, listNode);
            }
            listNode.addAfter(head);
        }

        public static class ListNode {
            int key;
            int val;
            ListNode pre;
            ListNode next;

            ListNode() {
            }

            ListNode(int key, int val) {
                this.key = key;
                this.val = val;
            }

            ListNode del() {
                this.pre.next = this.next;
                this.next.pre = this.pre;
                this.pre = null;
                this.next = null;
                return this;
            }

            void addAfter(ListNode node) {
                node.next.pre = this;
                this.next = node.next;
                node.next = this;
                this.pre = node;
            }

            void addBefore(ListNode node) {
                node.pre.next = this;
                this.pre = node.pre;
                node.pre = this;
                this.next = node;
            }

        }

    }

}
